package com.jcy_lyh.searchingsorting;

import android.content.Intent;
import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.view.View;
import android.widget.Button;
import android.widget.EditText;
import android.widget.Toast;

public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        final EditText input = findViewById(R.id.editText);
        final EditText SearchItem = findViewById(R.id.editText1);

        Button linearSearch = findViewById(R.id.button1);
        Button binarySearch = findViewById(R.id.button2);
        Button InsertionSearch = findViewById(R.id.button3);
        Button fibonacciSearch = findViewById(R.id.button4);
        Button blockSearch = findViewById(R.id.button5);
        Button ToSorting = findViewById(R.id.button6);




        ToSorting.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                Intent intent = new Intent(MainActivity.this, SecondActivity.class);
                startActivity(intent);
            }
        });


        //线性查找-----
        linearSearch.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                class Searching {
                    public  boolean linearSearch(int[] data, int min, int max, int target)
                    {
                        int index = min;
                        boolean found = false;

                        while (!found && index <= max)
                        {
                             if(data[index]==target)
                                 found =true;
                             else
                                 found =false;
                            index++;
                        }

                        return found;
                    }
                    //顺序查找
                    public  <T extends Comparable<T>> boolean SequenceSearch(T[] data, int min, int max, T target) {
                        int index = min;
                        boolean found = false;
                        while (!found && index <= max) {
                            found = data[index].equals(target);
                            index++;
                        }
                        return found;
                    }
                    //二分查找
                    public  int binarySearch(int[] array, int searchKey) {

                        int low = 0;
                        int high = array.length - 1;
                        while (low <= high) {
                            int middle = (low + high) / 2;
                            if (searchKey == array[middle]) {
                                return middle;
                            } else if (searchKey < array[middle]) {
                                high = middle - 1;
                            } else {
                                low = middle + 1;
                            }
                        }
                        return -1;
                    }
                    //插值查找
                    public  int InsertionSearch(int[] a, int value, int low, int high) {
                        int mid = low + (value - a[low]) / (a[high] - a[low]) * (high - low);
                        if (a[mid] == value)
                            return mid;
                        if (a[mid] > value)
                            return InsertionSearch(a, value, low, mid - 1);
                        else
                            return InsertionSearch(a, value, mid + 1, high);
                    }
                    //斐波那契查找算法
                    public  boolean fibonacciSearch(int[] table, int keyWord) {
                        //确定需要的斐波那契数
                        int i = 0;
                        while (getFibonacci(i) - 1 == table.length) {
                            i++;
                        }
                        //开始查找
                        int low = 0;
                        int height = table.length - 1;
                        while (low <= height) {
                            int mid = low + getFibonacci(i - 1);
                            if (table[mid] == keyWord) {
                                return true;
                            } else if (table[mid] > keyWord) {
                                height = mid - 1;
                                i--;
                            } else if (table[mid] < keyWord) {
                                low = mid + 1;
                                i -= 2;
                            }
                        }
                        return false;
                    }

                    //得到第n个斐波那契数
                    public  int getFibonacci(int n) {
                        int res = 0;
                        if (n == 0) {
                            res = 0;
                        } else if (n == 1) {
                            res = 1;
                        } else {
                            int first = 0;
                            int second = 1;
                            for (int i = 2; i <= n; i++) {
                                res = first + second;
                                first = second;
                                second = res;
                            }
                        }
                        return res;
                    }
                    //树表查找
                    public  <T extends Comparable<? super T>>
                    boolean binaryTreeSearch(T[] data, int min, int max, T target)
                    {
                        boolean found = false;
                        LinkedBinarySearchTree linkedBinarySearchTree = new LinkedBinarySearchTree();
                        // Comparable<T> comparableElement = (Comparable<T>)target;
                        for (int i=min;i<=max;i++)
                            linkedBinarySearchTree.addElement(data[i]);

                        while (found==false&&linkedBinarySearchTree.root!=null) {
                            if (target.equals(linkedBinarySearchTree.root.getElement())){
                                found = true;
                            }
                            else
                            {
                                if (target.compareTo((T)linkedBinarySearchTree.root.getElement()) < 0)
                                    linkedBinarySearchTree.root = linkedBinarySearchTree.root.left;
                                else
                                    linkedBinarySearchTree.root = linkedBinarySearchTree.root.getRight();
                            }
                        }
                        return found;
                    }
                    //分块查找
                    public   boolean BlockSearch(int[] data, int min, int max,int target) {
                        boolean found = false;
                        int area = block(data,min,max);
                        int leftarea = block(data,min,area-1);
                        int rightarea = block(data,area+1,max);

                        if (target==data[area])
                            found = true;
                        else
                        {
                            if (target<data[area])
                            {
                                if (target==data[leftarea])
                                    found = true;
                                else
                                {
                                    if (target<data[leftarea])
                                        found =  linearSearch(data,min,leftarea-1,target);
                                    else
                                        found =  linearSearch(data,leftarea+1,area-1,target);
                                }
                            }
                            else
                            {
                                if (target==data[rightarea])
                                    return true;
                                else
                                {
                                    if (target<data[rightarea])
                                        found = linearSearch(data,area+1,rightarea-1,target);
                                    else
                                        found = linearSearch(data,rightarea+1,max,target);
                                }
                            }
                        }
                        return found;
                    }

                    private  int block(int[] data, int min, int max)
                    {
                        int partitionelement;
                        int left, right;
                        int middle = (min + max) / 2;


                        partitionelement = data[middle];

                        swap(data, middle, min);

                        left = min;
                        right = max;

                        while (left < right)
                        {
                            while (left < right && data[left]<=partitionelement)
                                left++;
                            while (data[right]>partitionelement)
                                right--;
                            if (left < right)
                                swap(data, left, right);
                        }

                        swap(data, min, right);

                        return right;
                    }

                    private void swap(int[] data, int index1, int index2)
                    {
                        int temp = data[index1];
                        data[index1] = data[index2];
                        data[index2] = temp;
                    }
                }


                String m = String.valueOf(input.getText().toString());
                String index[] = m.split(",");
                final int[] index1 = new int[index.length];
                for(int i=0;i<index.length;i++)
                {
                    index1[i] = Integer.parseInt(index[i]);
                }
                final int target = Integer.valueOf(SearchItem.getText().toString());
                Searching a = new Searching();
                if(a.linearSearch(index1,0,index1.length-1,target)==true)
                    Toast.makeText(MainActivity.this, "查找成功", Toast.LENGTH_LONG).show();
                else
                    Toast.makeText(MainActivity.this, "查找失败", Toast.LENGTH_LONG).show();
            }
    });
//-------------------------------------------------------------------------------------------------------------------------------
        //二分查找
        binarySearch.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                class Searching
                {
                    //二分查找
                    public  int binarySearch(int[] array, int searchKey) {

                        int low = 0;
                        int high = array.length - 1;
                        while (low <= high) {
                            int middle = (low + high) / 2;
                            if (searchKey == array[middle]) {
                                return middle;
                            } else if (searchKey < array[middle]) {
                                high = middle - 1;
                            } else {
                                low = middle + 1;
                            }
                        }
                        return -1;
                    }
                }
                String m = String.valueOf(input.getText().toString());
                String index[] = m.split(",");
                final int[] index1 = new int[index.length];
                for(int i=0;i<index.length;i++)
                {
                    index1[i] = Integer.parseInt(index[i]);
                }
                final int target = Integer.valueOf(SearchItem.getText().toString());
                    Searching a = new Searching();
                if(a.binarySearch(index1,target)==-1)
                            Toast.makeText(MainActivity.this, "查找失败", Toast.LENGTH_LONG).show();
                else
                        Toast.makeText(MainActivity.this, "查找成功", Toast.LENGTH_LONG).show();
                }
        });
//-------------------------------------------------------------------------------------------------------------------------------
   //插值查找
  InsertionSearch.setOnClickListener(new View.OnClickListener() {
                @Override
                public void onClick(View v) {
                    class Searching {

                        //插值查找
                        public int InsertionSearch(int[] a, int value, int low, int high) {
                            int mid = low + (value - a[low]) / (a[high] - a[low]) * (high - low);
                            if (a[mid] == value)
                                return mid;
                            if (a[mid] > value)
                                return InsertionSearch(a, value, low, mid - 1);
                            else
                                return InsertionSearch(a, value, mid + 1, high);
                            }

                    }

                    String m = String.valueOf(input.getText().toString());
                    String index[] = m.split(",");
                    final int[] index1 = new int[index.length];
                    for(int i=0;i<index.length;i++)
                    {
                        index1[i] = Integer.parseInt(index[i]);
                    }
                    final int target = Integer.valueOf(SearchItem.getText().toString());
                    Searching a = new Searching();
                    if(a.InsertionSearch(index1,target,0,index1.length-1)==-1)
                        Toast.makeText(MainActivity.this, "查找失败", Toast.LENGTH_LONG).show();
                    else
                        Toast.makeText(MainActivity.this, "查找成功", Toast.LENGTH_LONG).show();
                }
        });

//---------------------------------------------------------------------------------------------------------------------------
       //斐波那契查找算法
        fibonacciSearch.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                class Searching {
                    //斐波那契查找算法
                    public  boolean fibonacciSearch(int[] table, int keyWord) {
                        //确定需要的斐波那契数
                        int i = 0;
                        while (getFibonacci(i) - 1 == table.length) {
                            i++;
                        }
                        //开始查找
                        int low = 0;
                        int height = table.length - 1;
                        while (low <= height) {
                            int mid = low + getFibonacci(i - 1);
                            if (table[mid] == keyWord) {
                                return true;
                            } else if (table[mid] > keyWord) {
                                height = mid - 1;
                                i--;
                            } else if (table[mid] < keyWord) {
                                low = mid + 1;
                                i -= 2;
                            }
                        }
                        return false;
                    }
                    //得到第n个斐波那契数
                    public  int getFibonacci(int n) {
                        int res = 0;
                        if (n == 0) {
                            res = 0;
                        } else if (n == 1) {
                            res = 1;
                        } else {
                            int first = 0;
                            int second = 1;
                            for (int i = 2; i <= n; i++) {
                                res = first + second;
                                first = second;
                                second = res;
                            }
                        }
                        return res;
                    }

                }

                String m = String.valueOf(input.getText().toString());
                String index[] = m.split(",");
                final int[] index1 = new int[index.length];
                for(int i=0;i<index.length;i++)
                {
                    index1[i] = Integer.parseInt(index[i]);
                }
                final int target = Integer.valueOf(SearchItem.getText().toString());
                Searching a = new Searching();
                if(a.fibonacciSearch(index1,target)==true)
                    Toast.makeText(MainActivity.this, "查找成功", Toast.LENGTH_LONG).show();
                else
                    Toast.makeText(MainActivity.this, "查找失败", Toast.LENGTH_LONG).show();
            }
    });
 //----------------------------------------------------------------------------------------------------------------------------
        //分块查找
        blockSearch.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                class Searching {
                    public  boolean linearSearch(int[] data, int min, int max, int target)
                    {
                        int index = min;
                        boolean found = false;

                        while (!found && index <= max)
                        {
                            if(data[index]==target)
                                found =true;
                            else
                                found =false;
                            index++;
                        }

                        return found;
                    }
                    //分块查找
                    public   boolean BlockSearch(int[] data, int min, int max,int target) {
                        boolean found = false;
                        int area = block(data,min,max);
                        int leftarea = block(data,min,area-1);
                        int rightarea = block(data,area+1,max);

                        if (target==data[area])
                            found = true;
                        else
                        {
                            if (target<data[area])
                            {
                                if (target==data[leftarea])
                                    found = true;
                                else
                                {
                                    if (target<data[leftarea])
                                        found =  linearSearch(data,min,leftarea-1,target);
                                    else
                                        found =  linearSearch(data,leftarea+1,area-1,target);
                                }
                            }
                            else
                            {
                                if (target==data[rightarea])
                                    return true;
                                else
                                {
                                    if (target<data[rightarea])
                                        found = linearSearch(data,area+1,rightarea-1,target);
                                    else
                                        found = linearSearch(data,rightarea+1,max,target);
                                }
                            }
                        }
                        return found;
                    }

                    private  int block(int[] data, int min, int max)
                    {
                        int partitionelement;
                        int left, right;
                        int middle = (min + max) / 2;


                        partitionelement = data[middle];

                        swap(data, middle, min);

                        left = min;
                        right = max;

                        while (left < right)
                        {
                            while (left < right && data[left]<=partitionelement)
                                left++;
                            while (data[right]>partitionelement)
                                right--;
                            if (left < right)
                                swap(data, left, right);
                        }

                        swap(data, min, right);

                        return right;
                    }

                    private void swap(int[] data, int index1, int index2)
                    {
                        int temp = data[index1];
                        data[index1] = data[index2];
                        data[index2] = temp;
                    }
                }

                String m = String.valueOf(input.getText().toString());
                String index[] = m.split(",");
                final int[] index1 = new int[index.length];
                for(int i=0;i<index.length;i++)
                {
                    index1[i] = Integer.parseInt(index[i]);
                }
                final int target = Integer.valueOf(SearchItem.getText().toString());
                Searching a = new Searching();
                if(a.BlockSearch(index1,0,index1.length-1,target)==true)
                    Toast.makeText(MainActivity.this, "查找成功", Toast.LENGTH_LONG).show();
                else
                    Toast.makeText(MainActivity.this, "查找失败", Toast.LENGTH_LONG).show();
            }
        });

    }
}
